// 快速排序算法，预先随机数种子交换，防止向冒泡排序方向退化

// 暴露接口
export function quickSort(nums: number[]): number[] {
    return recursion(nums, 0, nums.length - 1);
};

// 交换函数
function swap(nums: number[], index1: number, index2: number): void {
    let temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}

// 快速排序--->递归二分的过程
function recursion(nums: number[], left: number, right: number): number[] {
    // 递归出口：只剩一个元素时直接返回
    if (left >= right) {
        return nums;
    }
    const basis = partition(nums, left, right);// 快速选择算法求轴点
    recursion(nums, left, basis - 1);// [left,basis - 1]仍然无序
    recursion(nums, basis + 1, right);// [basis + 1,right]仍然无序
    return nums;
}

// 快速选择算法--->通过计算来返回轴点
function partition(nums: number[], left: number, right: number) {
    // 随机选择一个基准元素，防止极端情况向冒泡排序退化
    swap(nums, left, Math.floor(Math.random() * (right - left + 1) + left));
    const pivot = nums[left];
    let lastLow = left;// 小于等于元素区间的尾指针
    for (let i = left + 1; i <= right; i++) {
        // 如果当前元素小于等于基准元素，交换到小于等于元素区间
        if (nums[i] <= pivot) {
            swap(nums, i, lastLow + 1);
            lastLow++;// 因为小于等于的区间扩大，此时指针右滑
        }
    }
    // 选择算法完成后，把基准元素利用坐标（left）换到正确位置
    swap(nums, left, lastLow);
    return lastLow;// 此时lastlow就是最终正确的有序坐标
}


// 快速排序测试
console.log(quickSort([1, 2, 3, 4, 2, 3, 9, 3, 1, 4]));
console.log(quickSort([7, 2, 3, 4, 3, 2, 3, 9, 3, 1, 4]));
console.log(quickSort([7]));
console.log(quickSort([]));